package algorithm.careercup150.char1datastructure.arrayandstring.q1uniquechar;

/**
Implement an algorithm to determine if a string has all unique characters. What
if you cannot use additional data structures?  using array
 */
public class UniqueChar1 {
  public static void main(String[] args){
    String s = "abcd";


    System.out.print(isUnique(s));
    System.out.print(isUniqueBit32(s));
    System.out.print(isUniqueBit256(s));
  }
  private static boolean isUnique(String s){
    boolean[] letters = new boolean[256];
    int len = s.length(), index;
    for(int i = 0; i < len; i++){
      index = s.charAt(i);
      if(letters[index]) return false;
      letters[index] = true;
    }
    return true;
  }

  private static boolean isUniqueBit32(String s){
    int check = 0;
    int len = s.length(), bit;
    for(int i = 0; i < len; i++){
      bit = s.charAt(i)-'a';
      if((check & (1 << bit)) > 0) return false;
      check |= 1<<bit;
    }
    return true;
  }

  private static boolean isUniqueBit256(String s){
    int[] check = new int[8];
    int len = s.length(), index,bit, c;
    for(int i = 0; i < len; i++){
      c = s.charAt(i);
      index = c/32;
      bit = c%32;
      bit = s.charAt(i);
      if((check[index] & (1 << bit)) > 0) return false;
      check[index] |= 1<<bit;
    }
    return true;
  }

}
